// 力扣33. 搜索旋转排序数组
// https://leetcode.cn/problems/search-in-rotated-sorted-array/
package main

import "fmt"

func search(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	//搜索区间 [left,right]
	for left <= right {
		mid := (left + right) / 2 //获得区间[left,right]的中间位置
		if nums[mid] == target {  //如果刚好命中,直接返回
			return mid
		}
		if nums[mid] <= nums[right] { //mid和right在同一边
			if nums[mid] < target && nums[right] >= target { //target在mid的右边
				left = mid + 1
			} else { //target在mid的左边
				right = mid - 1
			}
		} else { //mid和right不在同一边
			if nums[left] <= target && target < nums[mid] { //target在mid的左边
				right = mid - 1
			} else { //target在mid的右边
				left = mid + 1
			}
		}
	}
	return -1
}

func main() {
	fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 0)) //4
	fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 3)) //-1
}
